/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 
 //循环遍历比较两个链表，谁小谁就尾插到新链表当中，谁尾插谁加加，
 //最后在判断一下有没有没比的，全放在新链表的最后
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    // 创建一个虚拟头节点
    struct ListNode dummy;
    struct ListNode* tail = &dummy;
    dummy.next = NULL;

    // 循环遍历比较
    while (list1 && list2) {
        if (list1->val < list2->val) {
            tail->next = list1;
            list1 = list1->next;
        }
        else {
            tail->next = list2;
            list2 = list2->next;
        }
        tail = tail->next;
    }

    // 连接剩余节点
    if (list1 != NULL) {
        tail->next = list1;
    }
    else {
        tail->next = list2;
    }

    return dummy.next;
}